package 排序;

import 排序.tools.Integers;

public class CountingSort extends Sort<Integer> {

	/*@Override
	protected void sort() {
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
			}
		}
		int[] counts = new int[max + 1];
		for (int i = 0; i < array.length; i++) {
			counts[array[i]]++;
		}
		
		int index = 0;
		for (int i = 0; i < counts.length; i++) {
			while (counts[i]-- > 0) {
				array[index++] = i;
			}
		}
	}*/
	
	/**
	 * 优化
	 */
	@Override
	protected void sort() {
		int min = array[0];
		int max = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[i] < min) {
				min = array[i];
			}
			if (array[i] > max) {
				max = array[i];
			}
		}
		
		int[] counts = new int[max - min + 1];
		for (int i = 0; i < array.length; i++) {
			counts[array[i] - min]++;
		}
		for (int i = 1; i < counts.length; i++) {
			counts[i] += counts[i - 1];
		}
		
		Integer[] newArray = new Integer[array.length];
		for (int i = array.length - 1; i >= 0; i--) {
			newArray[--counts[array[i] - min]] = array[i];
		}
		
		for (int i = 0; i < array.length; i++) {
			array[i] = newArray[i];
		}
	}
	

	public static void main(String[] args) {
		/*
		 * Integer[] array = Integers.random(10, 0, 15);
		 * Integers.println(array);
		 * sort1(array);
		 * Integers.println(array);
		 */
		test1();
	}

	private static void test1() {
		Person[] persons = new Person[6];
		persons[0] = new Person("A", 18);
		persons[1] = new Person("B", 10);
		persons[2] = new Person("C", 18);
		persons[3] = new Person("D", 10);
		persons[4] = new Person("E", 5);
		persons[5] = new Person("F", 3);

		// 找到最大值, 最小值
		int min = persons[0].age;
		int max = persons[0].age;
		for (int i = 0; i < persons.length; i++) {
			if (persons[i].age < min) {
				min = persons[i].age;
			}
			if (persons[i].age > max) {
				max = persons[i].age;
			}
		}

		// 构建计数数组
		int[] counts = new int[max - min + 1];
		for (int i = 0; i < persons.length; i++) {
			counts[persons[i].age - min]++;
		}
		for (int i = 1; i < counts.length; i++) {
			counts[i] += counts[i - 1];
		}

		// 排序
		Person[] newArray = new Person[persons.length];
		for (int i = persons.length - 1; i >= 0; i--) {
			newArray[--counts[persons[i].age - min]] = persons[i];
		}

		for (int i = 0; i < newArray.length; i++) {
			persons[i] = newArray[i];
		}

		for (int i = 0; i < persons.length; i++) {
			System.out.println(persons[i]);
		}
	}

	private static class Person {
		String name;
		int age;

		public Person(String name, int age) {
			this.name = name;
			this.age = age;
		}

		@Override
		public String toString() {
			return "Person [name=" + name + ", age=" + age + "]";
		}

	}

	

}
